/*
 * @author: wizardc
 */

using System.Collections.Generic;
using UnityEngine;

namespace Dou.Pathfinding
{
    /// <summary>
    /// 基于正方形的 A 星寻路格子工具类
    /// </summary>
    public static class AStarGridUtil
    {
        private static readonly List<AStarNode> _temp1 = new List<AStarNode>();
        private static readonly List<AStarGridNode> _temp2 = new List<AStarGridNode>();
        private static readonly List<AStarGridNode> _temp3 = new List<AStarGridNode>();
        
        /// <summary>
        /// 获取仅包含平滑关键点的路径列表
        /// </summary>
        public static bool FindSmootherPath(AStar aStar, AStarGrid grid, List<AStarGridNode> path)
        {
            if (!aStar.Pathfinding(grid, _temp1))
            {
                return false;
            }

            for (int i = 0; i < _temp1.Count; i++)
            {
                _temp2.Add((AStarGridNode) _temp1[i]);
            }
            
            if (_temp2.Count < 3)
            {
                AppendToPath(_temp2, path);
                Clear();
                return true;
            }
            
            BuildKeyPoint(_temp2, _temp3);
            _temp2.Clear();
            
            if (_temp3.Count < 3)
            {
                AppendToPath(_temp3, path);
                Clear();
                return true;
            }

            BuildSmoothPoint(grid, _temp3, _temp2);
            AppendToPath(_temp2, path);
            Clear();
            return true;
        }

        private static void AppendToPath(List<AStarGridNode> path, List<AStarGridNode> result)
        {
            for (int i = 0; i < path.Count; i++)
            {
                result.Add(path[i]);
            }
        }

        private static void BuildKeyPoint(List<AStarGridNode> path, List<AStarGridNode> result)
        {
            result.Add(path[0]);
            var offsetX = path[0].x - path[1].x;
            var offsetY = path[0].y - path[1].y;
            var len = path.Count - 1;
            for (var i = 1; i < len; i++)
            {
                var ox = path[i].x - path[i + 1].x;
                var oy = path[i].y - path[i + 1].y;
                if (ox != offsetX || oy != offsetY)
                {
                    result.Add(path[i]);
                    offsetX = ox;
                    offsetY = oy;
                }
            }
            result.Add(path[len]);
        }

        private static void BuildSmoothPoint(AStarGrid grid, List<AStarGridNode> path, List<AStarGridNode> result)
        {
            result.Add(path[0]);
            var len = path.Count;
            var nowIndex = 0;
            var testIndex = 2;
            while (testIndex < len)
            {
                if (!CanPass(grid, path[nowIndex], path[testIndex]))
                {
                    result.Add(path[testIndex - 1]);
                    nowIndex = testIndex - 1;
                    testIndex++;
                }
                else
                {
                    testIndex++;
                }
            }
            result.Add(path[len - 1]);
        }

        private static bool CanPass(AStarGrid grid, AStarGridNode start, AStarGridNode end)
        {
            var x = start.x;
            var y = start.y;
            var w = end.x - start.x;
            var h = end.y - start.y;
            var dx1 = w < 0 ? -1: (w > 0 ? 1 : 0);
            var dy1 = h < 0 ? -1: (h > 0 ? 1 : 0);
            var dx2 = w < 0 ? -1: (w > 0 ? 1 : 0);
            var dy2 = 0;
            var fastStep = Mathf.Abs(w);
            var slowStep = Mathf.Abs(h);
            if (fastStep <= slowStep)
            {
                fastStep = Mathf.Abs(h);
                slowStep = Mathf.Abs(w);
                dx2 = 0;
                dy2 = h < 0 ? -1 : (h > 0 ? 1 : 0);
            }
            var numerator = fastStep >> 1;
            for (var i = 0; i <= fastStep; i++)
            {
                if (!(x == start.x && y == start.y))
                {
                    if (!grid.GetWalkable(x, y))
                    {
                        return false;
                    }
                }
                numerator += slowStep;
                if (numerator >= fastStep)
                {
                    numerator -= fastStep;
                    x += dx1;
                    y += dy1;
                }
                else
                {
                    x += dx2;
                    y += dy2;
                }
            }
            return true;
        }

        private static void Clear()
        {
            _temp1.Clear();
            _temp2.Clear();
            _temp3.Clear();
        }
    }
}
